/*
 * @Author: your name
 * @Date: 2024-03-25 13:29:15
 * @LastEditTime: 2024-03-27 09:38:43
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\76.最小覆盖子串.cpp
 */
/*
 * @lc app=leetcode.cn id=76 lang=cpp
 *
 * [76] 最小覆盖子串
 */

// @lc code=start
class Solution {
public:
    bool check(unordered_map<char, int>& map){
        for(auto x:map){//遍历整个map，输出key及其对应的value值
            if(x.second > 0){
                return false;
            }
            
        }
        return true;
    }
    string minWindow(string s, string t) {
        string ans = "";
        int s_len = s.size();
        int t_len = t.size();
        int left = -1, right = 0;
        int min_len = INT32_MAX;
        if(s_len < t_len) return ans;
        // 存放s中字符串的位置，该字符串出现在t中
        queue<int> index_queue;
        // 存放t中各字符的个数，若为正数表示还需要map[i]个字符，为负数则表示多了。
        unordered_map<char, int> map;
        unordered_map<int ,int > ans_map;// 最短长度映射到left坐标
        //统计t中的字符数
        for(char tt:t){
            // 已有键值对
            if(map.find(tt) != map.end()){
                map[tt]++;
            }
            else{
                map[tt] = 1;
            }
        }
        for(right = 0; right < s_len; right++){
            char tmp_chr = (char)s[right];
            // 说明这个字符是t中有的
            if(map.find(tmp_chr) != map.end()){
                map[tmp_chr]--;
                // 第一次给left赋值
                if(left == -1){
                    left = right;
                }
                // 将字符下标入队
                index_queue.push(right);
                if(check(map)){
                    // 说明此时已经s已经包含了t
                    // 计算长度
                    if(min_len > (right-left+1)){
                        min_len = (right-left+1);
                        ans_map[min_len] = left;
                    }                   
                    // 尝试移动left
                    
                    while(1){
                        left = index_queue.front();
                        map[(char)s[left]]++;
                        if(!check(map)){
                            // 表示去掉left所在的字符，map check就不通过了
                            map[(char)s[left]]--;
                            if(min_len > (right-left+1)){
                                min_len = (right-left+1);
                                ans_map[min_len] = left;
                            }   
                            break;
                        }else{
                            index_queue.pop();
                            if(min_len > (right-left+1)){
                                min_len = (right-left+1);
                                ans_map[min_len] = left;
                        }   
                        }
                        
                    }
                        
                        
                    
                }
                
            }
        }  
        return min_len == INT32_MAX? ans:s.substr(ans_map[min_len],min_len); 

        
    }
};
// @lc code=end

// 有思路了！